For example, a prior art error correction method for use with quantum cryptography is disclosed in “INTRODUCTION TO QUANTUM COMPUTATION AND INFORMATION” (EDITOR: Hoi-Kwong Lo, et al.). Some protocols defining procedures are proposed to implement the quantum cryptography, and among them BB84 protocol is currently assumed to be a standard protocol for the quantum cryptography. After that, this protocol has been improved and is provided as a protocol effective even in noisy realistic communication paths. The improved BB84 protocol described in “Experimental Quantum Cryptography” (C. H. Bennett, F. Bessette, G. Brassard, L. Salvail and J. Smolin, J. Cryptology Vol.5, pp.3-28) roughly consists of two parts: a first procedure for sharing physically-safe initial data using a quantum communication path and a second procedure for correcting errors included in the initial data by using an error correction method on a public line (i.e., a classical path), and for reducing a volume of information leaking to third parties in terms of information theory. The first procedure of roughly sharing data by using a quantum communication path is unrelated directly to the present invention. The BB84 protocol is referred to as this improved BB84 protocol from here on. The present invention relates to “the second procedure for correcting errors included in the initial data, and for reducing a volume of information leaking to third parties in terms of information theory”. The prior art method can be explained as follows.
With the current state of the art, the shared data that appear in the first half of the BB84 protocol include errors that occur at a rate of about 1%. These errors result from the accuracy or the like of the apparatus that is affected by fluctuations, such as thermal noise, and reflected light, which appear in the communication path. Third party involvement can also cause an error. Although the biggest feature of the quantum cryptography is that it is possible to detect third party involvement as an error, that may be true under ideal circumstances. As previously mentioned, it is impossible at this stage to judge whether the occurrence of an error is caused by a leakage that blends into the level of a rate of errors caused spontaneously or by third party involvement. Furthermore, although according to the BB84 protocol the transmitter roughly shares data with the receiver, the system does not properly function in most cases if the shared data include errors that occur at a rate as much as 1%. When the shared data is used as key data in common key cryptographic scheme, for example, it is to be understood at once that even a single-bit error is not included in the shared data. To solve this problem, there has been provided a method of removing errors while preventing information from leaking to wiretappers as much as possible, simultaneously throwing away information leaked during quantum communications, and sharing only safe data between the transmitter and the receiver. This method is called error correction and privacy amplification.
The principle of the error correction method is simple. In accordance with the method, it is assumed that there is shared data containing some errors between the transmitter and the receiver. The shared data is divided into some blocks, and single-bit parities are compared with each other for each block. At this time, because a public line is used, it can be generally assumed that the parity information can be also leaked to wiretappers. Therefore, in this case the volume of leaked information is 1 bit in terms of information theory, and 1 bit of the roughly-shared data being held now is thrown away to make them balance each other out. The processing on blocks whose parities agree with those of corresponding blocks is then terminated for the time being. Each block whose parity does not agree with that of the corresponding block is further divided into equal halves, and a similar parity check is then performed on each of them. Two-branch searching is repeatedly carried out until an erroneous bit is detected, and this erroneous bit is finally corrected. Thus, (the number of parity bits used for the two-branch searching+1) bits are thrown away, and remaining bits are defined as a candidate of the shared information. This is because when an even number of errors are included in each block of the shared data the parities agree with each other between the shared data being held by the transmitter and that being held by the receiver and no error cannot be detected, and therefore in accordance with the prior art method bits of the shared data are appropriately inverted and erroneous bits are surely removed by repeating the same processing from the beginning several times. In accordance with the privacy amplification method, even if the above-mentioned error correction is carried out, there is a possibility that there exist bits that have not been detected as erroneous bits even when a wiretapper taps the shared data, though the bits are few in number. To prevent the possibility of part of the information being tapped, each of the transmitter and the receiver carries out a process of further improving the safety by implementing a hash operation on the shared information and assuming the hash value as final shared data. This method is the so-called privacy amplification method.
A t-resilient function for use in the prior art method will be explained hereafter.
f is a Boolean function: Z—2^n->Z—2^m (n>m), where Z—2 is Z2 and 2^n is the n-th power of 2.
By definition, the fact that f is balanced (or equitable) means that a reverse image f^{−1} (y) of f has 2^{n−m} elements for all m-bit strings y.
This definition is equivalent to the fact that when y is an output and an input x is chosen at random, P(y) becomes 2^{−m} for all m-bit strings y, assuming that the probability of f(x)=y is P(y). Then, assume that t bits of the input x input to f are fixed. In other words, assume thatx_{i—1}=c—1, . . . , x_{i_t}=c_twhere x_{i—1} is xi1 and c—1 is c1, and x_{i_t} is xit and c_t is ct.
Assume that P(y|x_{i—1}=c—1, . . . , x_{i_t}=c_t) is the probability of f(x)=y on condition that x_{i—1}=c—1, . . . , x_{i_t}=c_t.
By definition, the fact that f is correlation-immune of order t means that P(y|x_{i—1}=c—1, . . . , x_{i_t}=c_t)=P(y) is established for all x, y, c—1, c—2, . . . , and c_t.
In the above description, 2^{−m} means 2−m.
It is to be understood through intuition that even though t bits of the n-bit string x has come to light to a wiretapper, the probability that the wiretapper can estimate f(x)=y is made to become P(y)=2^{−m} after making f act on the n-bit string x. This probability is the same as that in the case where nothing has to come to light to the wiretapper. In other words, the probability is 2^{−m}. Regardless of whether or not t bits of the n-bit string x has come to light to the wiretapper, an m-bit shared key has an m-bit entropy (the estimated probability is 2^{−m}) by making f act on the n-bit string x when viewed from the wiretapper.
By definition, the fact that f is a t-resilient function means that f is balanced and is correlation-immune of order t.
This definition is equivalent to the fact that P(y|x_{i—1}=c—1, . . . , x_{i_t}=c_t)=2^{−m} is established for all possible variables.
It is to be understood through intuition that f is made to act on the n-bit string x even if some bits (t bits or less) of them have come to light to the wiretapper, so that the bit length of the shared key is shortened from n bits to m bits.
At this time, because some bits of x (i.e., the n-bit string) have come to light to the wiretapper, the probability of estimating the n-bit string x becomes smaller than 2^{−n} when viewed from the wiretapper. In other words, the complete safety is not achieved (the complete safety of the n-bit string x means that the probability of estimating the n-bit string x must be just 2^{−n}).
On the other hand, for y=f(x) (i.e., the m-bit string), the probability of the wiretapper estimating y is just 2^{−m}. In other words, there is entropy of m bits.
Therefore, t is assumed to be a maximum of the number of bits that can be tapped by Eve in the quantum communication while being buried in errors. Accordingly, the value of t must be determined according to the error rate.
Therefore, if n is determined, t is determined according to the error rate, the t-resilient function is constructed, and the communication protocol is designed so that m is sufficiently large, even if some bits are leaked to a wiretapper during initial key exchanging, the complete safety (the complete safety intuitively means that the probability that the wiretapper estimates a key of m bits must be just 2^{−m} if it is assumed that m to be a security parameter) can be achieved by using the t-resilient function.
By the way, a method of constructing the t-resilient function may be known to the wiretapper. In other words, the t-resilient function is public information.
A problem encountered with the prior art method is that while a t-resilient function is made to act on data to be transmitted to improve the safety of transmission, there doesn't exist a proper method of constructing the t-resilient function in all cases, depending on the bit length of the input data, the output bit length, and security parameters.
The present invention is proposed to solve the above-mentioned problem, and it is therefore an object of the present invention to provide a method that can deal with all the above-mentioned cases by using a general function, such as SHA-1, other than t-resilient functions.
It is another object of the present invention to provide a method that can make the safety when sending and receiving data result in the safety of the Vernam cipher encryption, and that provides higher safety in terms of information theory.